/**
 * https://leetcode.cn/submissions/detail/576995484/
 * 2376. 统计特殊整数
 * Hard, 黄伟杰 2024.10.30
 * 数位DP
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int countSpecialNumbers(int n)
    {
        string s = to_string(n);
        int m = s.length();
        vector<vector<int>> memo(m, vector<int>(1 << 10, -1));
        auto dfs = [&](auto &&dfs, int i, int mask, bool is_limit, bool is_num) -> int
        {
            if (i == m)
            {
                return is_num;
            }
            if (!is_limit && is_num && memo[i][mask] != -1)
            {
                return memo[i][mask];
            }
            int res = 0;
            if (!is_num)
            {
                res = dfs(dfs, i + 1, mask, false, false);
            }
            int up = is_limit ? s[i] - '0' : 9;
            for (int d = is_num ? 0 : 1; d <= up; d++)
            {
                if ((mask >> d & 1) == 0)
                {
                    res += dfs(dfs, i + 1, mask | (1 << d), is_limit && d == up, true);
                }
            }
            if (!is_limit && is_num)
            {
                memo[i][mask] = res;
            }
            return res;
        };
        return dfs(dfs, 0, 0, true, false);
    }
};